package string;

import org.junit.Test;

public class ValidParenthesisString678 {
    @Test
    public void test() {
        print("()");
        print("(*)");
        print("(*))");
        print("((*)");
        print("((*))");
        print("*))");
        print("*)(");
    }

    public void print(String s) {
        System.out.format("s: %s, valid: %s\n", s, checkValidString(s));
    }

    public boolean checkValidString(String s) {
        char[] cs = s.toCharArray();
        int l = 0; // count of "("
        int r = 0; // count of ")"
        int t = 0; // count of "*"

        // 正向扫描一遍
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            if (c == '(') {
                l++;
            } else if (c == ')') {
                r++;
            } else {
                t++;
            }
            if (r-l > t) {
                return false;
            }
        }

        // 逆向扫描一遍, 处理类似如下字符串: "*)("
        l = 0;
        r = 0;
        t = 0;
        for (int i = cs.length-1; i >= 0; i--) {
            char c = cs[i];
            if (c == '(') {
                l++;
            } else if (c == ')') {
                r++;
            } else {
                t++;
            }
            if (l-r > t) {
                return false;
            }
        }

        // 最终要求在有"*"的情况下, 完全匹配.
        if (Math.abs(r-l) > t) {
            return false;
        }

        return true;
    }
}
